<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>

</body>
<script>
    // 什么是计数排序，计数排序：找出这组数中的最大值，然后设置最大值+1个盒子，一次为从0 - 最大值，然后把数放到对应的盒子中，再按盒子的顺序把数据取出合并
    // 如果存在负值，可以使用偏移量，偏移量为-min
    /**
     * 使用计数排序算法对整数数组进行排序（升序）
     * 原理：通过计数数组统计每个元素出现次数，再重构有序数组
     * @param {number[]} arr - 待排序的整数数组（可包含负数）
     * @returns {number[]} 排序后的升序数组
     */
    function countSort(arr){
        // 计算偏移量：将负数转换为非负索引
        const min = Math.min(...arr)
        const offset = min > 0 ? 0 : -min  // 负数最小值时取绝对值，非负数则为0
        const max = Math.max(...arr) + offset  // 计算转换后的最大值

        // 初始化计数数组（索引范围：0 到 max）
        const countArray = new Array(max + 1).fill(0)

        // 统计元素出现频率（元素值+offset作为索引）
        for(let i = 0;i < arr.length;i++){
            const item = arr[i]
            countArray[item + offset]++
        }

        // 重构排序数组
        const result = []
        countArray.forEach((item,index) => {
            // 对出现次数大于0的元素，按频率填充到结果
            if(item > 0){
                // 将索引转换回原始值并重复添加
                result.push(...new Array(item).fill(index - offset))
            }
        })
        return result
    }
    let arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1,-10,-2,-1,-32, 4, 2, 4, 6, 9, 2];
    console.log(countSort(arr))
</script>
</html>